package cn.edu.njust.alg.leetcode;

/**
 * 创建时间：2015年6月15日 上午11:47:37 项目名称：AlgorithmExercise
 * 
 * @author Zhou Xiumin
 * @version 1.0
 * @since JDK 1.7.0_21 文件名称：Leetcode_0_t.java 类说明：
 */
public class Leetcode_151_Reverse_Words_in_a_String {

	public static void main(String[] args) {
		System.out.println(reverseWords(" 324"));
	}

	public static void reverse(char[] csr, int start, int end) {
		if (start == end) {
			return;
		}
		for (int i = start; i <= (end + start) / 2; i++) {
			char t = csr[i];
			csr[i] = csr[end + start - i];
			csr[end + start - i] = t;
		}
	}

	public static String reverseWords(String s) {
		if(s==null){
			return null;
		}
		s=s.trim();
		char[] csr = s.toCharArray();
		
		
		reverse(csr, 0, csr.length-1);
		int start=0;
		for (int i = 0; i < csr.length; i++) {
			if((i==0 &&csr[i]!=' ')||(i>0&&csr[i-1]==' '&&csr[i]!=' ')){
				start=i;
			}else if(i==csr.length-1 &&csr[i]!=' '){
				reverse(csr,start,i);
			}else if(i>1&&csr[i-1]!=' '&&csr[i]==' '){
				reverse(csr,start,i-1);
			}
		}
		return new String(csr);
	}
}
